#include "streamsummary.h"

StreamSummary::StreamSummary(int k) {
	this->k = k;
	this->min_bucket = -1;
}

void StreamSummary::add_item(int i, int j, float w) {
	int key = (int) ceil(w);
	cerr<< i << "," << j << "," << w << endl;
	ITEM_KEY item_key = ITEM_KEY();
	item_key.push_back(i);
	item_key.push_back(j);
	Item * item = new Item(item_key, w, 1.0);

	cerr<< "new item: " << (*item).toString() << endl;
	Bucket * _bucket;

	if (this->min_bucket == -1) {
		cerr<< "min_bucket == NULL" << endl;
		_bucket = new Bucket(key, NULL, NULL);
		(*item).parent = _bucket;
		this->items.insert(make_pair((*item).hashvalue, *item));

		(*_bucket).add(&this->items.find((*item).hashvalue)->second);
		this->buckets.insert(make_pair(key, *_bucket));
		this->min_bucket = (this->buckets.find(key)->second).key;
	} else if (this->buckets.find(key) == this->buckets.end()) {
		cerr<< "key == end()" << endl;
		Bucket tmp_bucket = this->buckets.find(this->min_bucket)->second;
		while (tmp_bucket.next != NULL && (*tmp_bucket.next).key < key) {
			tmp_bucket = *tmp_bucket.next;
		}

		_bucket = new Bucket(key, &tmp_bucket, NULL);
		this->buckets.insert(make_pair(key, *_bucket));
		if (tmp_bucket.next != NULL) {
			//(*_bucket).next = tmp_bucket.next;
			this->buckets.find((*_bucket).key)->second.next = this->buckets.find(tmp_bucket.key)->second.next;
			this->buckets.find((*tmp_bucket.next).key)->second.prev = &this->buckets.find(key)->second;
			//(*tmp_bucket.next).prev = &this->buckets.find(key)->second;
		}

		this->buckets.find(tmp_bucket.key)->second.next = &this->buckets.find(
				(*_bucket).key)->second;
		(*item).parent = _bucket;
		this->items.insert(make_pair((*item).hashvalue, *item));

	} else {
		(*item).parent = &this->buckets.find(key)->second;
		//cerr<< "bucket" <<  << endl;
		this->items.insert(make_pair((*item).hashvalue, *item));
		cerr<< "key exists: " << (this->buckets.find(key)->second).key<< endl ;
		this->buckets.find(key)->second.add(
				&this->items.find((*item).hashvalue)->second);
		//cerr<<  "item: parent" << ((*(*item).parent).key) << endl;
	}
}

void StreamSummary::increase(int i, int j, float w) {
	ITEM_KEY item_key = ITEM_KEY();
	item_key.push_back(i);
	item_key.push_back(j);
	Item * item = &this->items.find(hash_value(item_key))->second;
	Bucket * curr_bucket = (*item).parent;
	int curr_key = (*(*item).parent).key;
	cerr<< "item: " << (*item).toString() << (*(*item).parent).key  << endl;
	float new_weight = w + (*item).weight;
	int new_key = ceil(new_weight);
	this->items.find(hash_value(item_key))->second.weight = new_weight;
	(*item).weight = new_weight;
	Bucket * _bucket;
	cerr<< "item after update: " << (*item).toString() << endl;
	cerr<< "new key : " << new_key << endl;

	if (this->buckets.find(new_key) != this->buckets.end()) {
		cerr<< "new key exists" << endl;
		if ((*(*item).parent).key != new_key) {
			this->items.find((*item).hashvalue)->second.parent = &this->buckets.find(new_key)->second;
			this->buckets.find(new_key)->second.add(&this->items.find((*item).hashvalue)->second);
			this->buckets.find((*curr_bucket).key)->second.remove(&this->items.find((*item).hashvalue)->second);
			cerr<< "new key exists after delete " <<  this->buckets.find((*curr_bucket).key)->second.toString() << endl;
			//(*(*item).parent).remove(item);
		}
	} else {
		cerr<< "!new key exists" << endl;

		Bucket * tmp_bucket = curr_bucket;
		cerr<< "got parent: " << (tmp_bucket != NULL) << endl;
		while ((*tmp_bucket).next != NULL && (*(*tmp_bucket).next).key < new_key) {
			cerr<< "running while" << endl;
			tmp_bucket = (*tmp_bucket).next;
		}
		cerr <<"tmpvuket"  << this->buckets.find((*tmp_bucket).key)->second.toString() << endl;

		cerr<< "found insert loc: " << (*tmp_bucket).key << endl;
		_bucket = new Bucket(new_key,&this->buckets.find((*tmp_bucket).key)->second, NULL);
		(*_bucket).add(&this->items.find((*item).hashvalue)->second);
		this->buckets.insert(make_pair(new_key, *_bucket));

		if ((*tmp_bucket).next != NULL) {
			cerr << "*tmpbucket!= NULL" << endl;
			this->buckets.find((*(*tmp_bucket).next).key)->second.prev = &this->buckets.find(new_key)->second;
			this->buckets.find(new_key)->second.next = this->buckets.find((*tmp_bucket).key)->second.next;
			/*(*(*tmp_bucket).next).prev = _bucket;
			 (*_bucket).next = (*tmp_bucket).next;*/
		}

		this->buckets.find((*tmp_bucket).key)->second.next = &this->buckets.find(new_key)->second;
		this->items.find((*item).hashvalue)->second.parent = _bucket;
		this->buckets.find(curr_key)->second.remove(&this->items.find((*item).hashvalue)->second);
		cerr<< "!new key exists curr bucket after delete " <<  this->buckets.find(curr_key)->second.toString() << endl;
		cerr  << "new bucket " << (this->buckets.find(new_key)->second.toString()) << endl;
		//this->min_bucket = this->buckets.find(min_bucket)->second;
	}
	if (this->buckets.find(curr_key)->second.has_elements() == false) {
		cerr<< "curr bucket empty" << endl;
		if ((*curr_bucket).key == this->min_bucket) {
			cerr << "curr == min"  << endl;
			this->min_bucket = (*this->buckets.find(min_bucket)->second.next).key;
			//this->buckets.find((this->min_bucket)->second.prev = NULL;
			this->buckets.find(this->min_bucket)->second.prev = NULL;
		} else {
			cerr << "curr != min\n " << (this->buckets.find(curr_key)->second.toString()) << endl ;

			if (this->buckets.find((*curr_bucket).key)->second.next != NULL) {
				cerr << "curr.next != NULL " <<  (*this->buckets.find((*curr_bucket).key)->second.next).toString() << endl;
				cerr << "next.prev" <<  (*(*this->buckets.find((*curr_bucket).key)->second.next).prev).toString() << endl;
				cerr << "curr " <<  this->buckets.find(curr_key)->second.toString() << endl;
				cerr << "curr.next.key " << (*this->buckets.find((*curr_bucket).key)->second.next).key << endl;


				(*this->buckets.find((*curr_bucket).key)->second.next).prev = this->buckets.find((*curr_bucket).key)->second.prev;
				/*this->buckets.find((*(*curr_bucket).next).key)->second.prev =
				this->buckets.find((*curr_bucket).key)->second.prev;*/

			}

			this->buckets.find((*(*curr_bucket).prev).key)->second.next =
					this->buckets.find((*curr_bucket).key)->second.next;

			cerr << "empty bucket tostring:\n " <<  this->toString()<< endl;
		}

		this->buckets.erase((*curr_bucket).key);
	}

}
Item StreamSummary::get_min_el() {

	Bucket tmp_bucket = this->buckets.find(this->min_bucket)->second;
	cerr<< "get_min_el: " << tmp_bucket.toString()  << endl;

	//ITEM_SET::iterator it = this->buckets.find(min_bucket)->second.elements.begin();
	ITEM_SET::iterator it = tmp_bucket.elements.begin();
	cerr<< "init it: " << endl;
	Item _min = **it;
	it++;
	for (; it != tmp_bucket.elements.end(); it++) {
		if ((**it).weight < _min.weight) {
			_min = *(*it);
		}
	}

	return _min;
}

void StreamSummary::replace_min(int i, int j, float w) {
	cerr<< "replace min" << endl;
	Item min = this->get_min_el();
	cerr<< "got min" << endl;
	ITEM_KEY item_key = ITEM_KEY();
	item_key.push_back(i);
	item_key.push_back(j);
	Item * min_new = new Item(item_key, w + min.weight, min.weight);
	this->items.insert(make_pair((*min_new).hashvalue, *min_new));

	this->add_item(i, j, w);

	this->buckets.find(this->min_bucket)->second.remove(
			&this->items.find(min.hashvalue)->second);
	this->items.erase(min.hashvalue);

	if (!this->buckets.find(this->min_bucket)->second.has_elements()) {
		int old_key = this->min_bucket;

		this->min_bucket =
				(*this->buckets.find(this->min_bucket)->second.next).key;
		this->buckets.find(this->min_bucket)->second.prev = NULL;
		this->buckets.erase(old_key);
	}
}

const string StreamSummary::toString() {
	Bucket * tmp_bucket = &this->buckets.find(this->min_bucket)->second;
	ostringstream oss;

	while (tmp_bucket != NULL) {
		oss << (*tmp_bucket).toString() << endl;
		tmp_bucket = (*tmp_bucket).next;

	}
	return oss.str();
	/*BUCKET_MAP::iterator it =  this->buckets.find((*min_bucket).key);
	 ostringstream oss;
	 int count = 0;
	 for(;it != this->buckets.end(); it++) {
	 count++;
	 cerr<< "# " << count << endl;
	 oss << (*it).second.toString() << endl;
	 }*/

}

void StreamSummary::insert(int i, int j, float w) {
	if (this->items.find(hash_value(i, j)) != items.end()) {
		cerr<< "increase" << endl;
		this->increase(i, j, w);
	} else if (this->items.size() < this->k) {
		cerr<< "add" << endl;
		this->add_item(i, j, w);
	} else {
		cerr<< "replace" << endl;
		this->replace_min(i, j, w);
	}
}
/*
int main(int argc, char* argv[]) {
	printf("Running StreamSummary test\n");
	if (argc < 2) {
		printf("Invalid number parameters\n-i <inputfile> -k <spacesaving size>\n");
		return -1;
	}
	char * inputfile = argv[2];
	int k = atoi(argv[4]);

	printf("hello\n");
	for (int i = 1; i < argc; i++) {
		if (std::string::compare(argv[i],"-k")) {
			k = atoi(argv[i+1]);
			cerr << k << endl;
		} else if (std::string::compare(argv[i],"-i")) {


			inputfile = argv[i + 1];
		}
	}

	printf("world\n");
	printf("%s\n", inputfile);
	//printf ("%d\n",k);

	StreamSummary ss = StreamSummary(k);
	ifstream file(inputfile);
	string line;
	if (file.is_open()) {
		while(!file.eof()) {
			getline(file, line);
			vector < string > tokens;
			boost::split(tokens, line, boost::is_any_of("\t"));
			cerr << tokens[0] << "," << tokens[1] << endl;
			ss.insert(lexical_cast<int>(tokens[0]),lexical_cast<int>(tokens[0]),lexical_cast<float>(tokens[1]));
			cerr << ss.toString() << endl;
		}
	}

	file.close();
	cerr << "closed file" << endl;

		ss.insert(1,2,0.8);
	 cerr<< "ss: " <<  ss.toString() << endl;
	 ss.insert(2,2,0.25);
	 cerr<< "ss: " << ss.toString() << endl;
	 ss.insert(1,3,0.54);
	 cerr<< "ss: " <<  ss.toString() << endl;
	 ss.insert(1,2,0.34);
	 cerr<<   "ss final\n" <<  ss.toString() << endl;
	 cerr<< "#num el: " << ss.items.size() << endl;

	 cerr<< ss.min_bucket << endl;
	 cerr<< ss.buckets.size() << endl;

	 ITEM_MAP::iterator it = ss.items.begin();
	 for (;it != ss.items.end(); it++) {
	 cerr<< (*it).second.toString() << endl;
	 }

	cerr << "finished " << endl;
	return -1;
}
*/
